/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
// 区分计算过的值和未计算的值
var coinChange = function(coins, amount) {
  // 表示凑出面值为i的最少硬币个数为dp[i]，初始化为amount加1表示无效
  const dp = new Array(amount + 1).fill(amount + 1)
  dp[0] = 0
  for(let i = 1; i <= amount; i++) {
    for(let c of coins) {
      if(i - c >= 0 && dp[i - c] !== amount + 1) {
        dp[i] = Math.min(dp[i], 1 + dp[i - c])
      }
    }
  }
  if(dp[amount] == amount + 1) return -1
  return dp[amount]
};
// 求最少，应该反应过来BFS
var coinChange = function(coins, amount) {
  if(amount == 0) return 0
  const queue = []
  const visited = new Array(amount + 1).fill(false)
  queue.push(amount)
  visited[amount] = true
  coins.sort((a, b) => a - b)
  let ans = 1
  while(queue.length > 0) {
    let s = queue.length
    for(let i = 0; i < s; i++) {
      let tempAmount = queue.shift()
      for(let j = 0; j < coins.length; j++) {
        let temp = tempAmount - coins[j]
        if(temp == 0) return ans
        if(temp < 0) break
        if(!visited[temp]) {
          queue.push(temp)
          visited[temp] = true
        }
      }
    }
    ans++
  }
  return -1
}